﻿//632. 最小区间
//你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
//我们定义如果 b - a < d - c 或者在 b - a == d - c 时 a < c，则区间[a, b] 比[c, d] 小。




class Solution
{
public:
    bool check(vector<int>& arr)
    {
        for (auto& e : arr)
        {
            if (e <= 0)   return false;
        }
        return true;
    }

    vector<int> smallestRange(vector<vector<int>>& nums)
    {
        vector<pair<int, int>> arr;
        //合并
        for (int i = 0; i < nums.size(); i++)
        {
            for (auto& x : nums[i])
            {
                arr.push_back({ x,i });
            }
        }
        //排序
        sort(arr.begin(), arr.end());
        //计数数组
        vector<int> cnt(nums.size(), 0);

        int ans_l = arr[0].first;
        int ans_r = arr.back().first;

        int left = 0, right = -1;
        for (right = 0; right < arr.size(); right++)
        {
            cnt[arr[right].second]++;
            while (check(cnt))
            {
                if ((ans_r - ans_l) > (arr[right].first - arr[left].first))
                {
                    ans_l = arr[left].first;
                    ans_r = arr[right].first;
                }
                cnt[arr[left++].second]--;
            }
        }
        return { ans_l,ans_r };
    }
};